/*
    堆和优先队列
        优先队列底层用堆实现
		堆通常是一个可以被看做一棵完全二叉树的数组对象,堆总是满足下列性质：
		堆中某个节点的值总是不大于或不小于其父节点的值；
		堆总是一棵完全二叉树。

        堆有很多种实现方式但是O(logn)的操作基本都跟树有关
        堆可以理解成树
        满二叉树:除了叶子节点，每个节点都有左右孩子
        完全二叉树:把节点按照满二叉树一层一层往下放，剩下的节点从同层的左到右放过去，所以右边可能没节点

    二叉堆(完全二叉树实现的堆)
        堆中的某个节点的值总是不大于其父节点的值，所以根节点是最大的，这样的堆叫做最大堆，当然也有最小堆
        但并不是层次越高的节点，其值就一定越小

    最大堆
        由于元素是一层一层从上到下从左到右顺序挂接起来的，可以使用树存，也可以使用数组存
                         60     索引是0
                    40        30    索引是1 2  从左到右
                25     18  28    17     索引是3 4 5 6
             19   20                        索引是7 8

        使用数组存储，通过公式可以计算出index索引的父节点和左右子节点

    堆实现优先队列的原因
        堆,底层虽然用数组，但是数组中存的是树的形式，利用树的性质简化数组的复杂度，又保证了顺序性，且通过方法可以找到各个节点从而复现树

    add和extractMax 时间复杂度都是O(h) 即O(logn) 并且它永远不会退化成链表，因为底层是数组
 */
public class MaxHeap<E extends Comparable<E>> {

    //依赖动态数组
    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data= new Array<>();
    }

    //将数组变成堆---heapify
    //实现1；直接把传递进来的元素每次都调用add方法就好了，这样时间复杂度就是O(nlogn)
    //我们使用另外一种实现 时间复杂度为0(n)
    //把传递进来的数组先原封不动存好，然后找到最后一个非叶子节点,这样一下排除了很多叶子节点
    //然后从最后一个非叶子节点开始siftUp直到所有非叶子节点都siftUp结束。
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        //从第一个非叶节点开始，第一个非叶子节点就是最后一个节点的父亲节点
        for(int i = parent( arr.length-1); i>=0 ;i-- ){
            //直到所有非叶子节点都siftDown结束
            siftDown(i);
        }
    }

    public int size(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    //返回完全二叉树的数组表示中，index索引的父亲节点
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't no parent");
         return (index - 1) / 2;
    }

    //返回完全二叉树的数组表示中，index索引的左节点
    private int leftChild(int index){
        return index*2+1;
    }

    //返回完全二叉树的数组表示中，index索引的右节点
    private int rightChild(int index){
        return index*2+2;
    }

    // 向堆中添加元素
    public void add(E e){
        //向数组的末尾添加元素
        data.addLast(e);
        //这个刚被添加进去的元素要考虑元素上浮
        siftUp(data.getSize() - 1);
    }

    //元素上浮，如果新添加进来的元素比他的父亲节点还大就相互交换位置一直到根节点，让其保证最大堆的性质
    private void siftUp(int k){
        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    // 看堆中的最大元素
    public E findMax(){
        if(data.getSize() == 0)
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        return data.get(0);
    }

    // 取出堆中最大元素---每次把根节点返回出去，然后重新找根节点(整个堆开始下沉维持性质）
    public E extractMax(){
        E ret = findMax();

        //让根节点跟最后一个节点交互位置即最大的节点跟最后一个节点交换位置
        data.swap(0,data.getSize()-1);
        //把最后一个元素删掉
        data.removeLast();

        //删除根结点后堆性质被破坏，下沉元素维护性质
        siftDown(0);

        return ret;
    }

    //元素下沉，让其找到下一个根节点
    private void siftDown(int k){

        //索引是从0开始的，到达叶子节点就不需要下沉，叶子节点的左孩子一定下标越界，而且有孩子一定比左孩子大索引考虑左孩子即可
        while(leftChild(k) < data.getSize()){
            //找到k节点左右孩子中较大的元素是谁

            int j =leftChild(k);
            //如果左孩子索引+1即右孩子的索引  还小于长度，代表有右孩子
            //并且右孩子的值大于左孩子的值
            if( j + 1 <data.getSize() &&  data.get(j+1).compareTo(data.get(j))>0)
                j++;    //此时j里面存的就是右孩子的索引 也可以写成 j = rightChild(k)

            //此时data[j] 是K这个节点的rightChild和leftChild中的最大值

            //循环结束条件，当根元素比左右孩子中最大的都大，代表没违背堆的性质，就可以退出循环了
            if(data.get(k).compareTo(data.get(j)) >= 0 )
                break;

            //交互k 和 j 的元素
            data.swap(k, j);
            k = j;

        }

    }

    //取出堆中的最大元素，并且替换成元素e
    //其实实现方法可以先extractMax然后再add 但是就是两次O(logn)
    //我们可以让他跟根元素即最大的元素换下位置，然后siftDown即可 这样就只要一次O(logn)
    public E replace(E e){
        E ret = findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }




}
